/*
 * @Autor: taobo
 * @Date: 2020-06-08 16:15:20
 * @LastEditTime: 2020-06-08 17:20:25
 */ 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//数组能否分成两组，使得两组中各元素加起来的和相等，动态规划，也可以使用回溯解法
class split_1{
public:
    bool operator()(vector<int>& nums){
        int sum = 0;
        for(int& val:nums) sum += val;
        if(sum & 1) return false;
        int row = nums.size();
        int col = sum/2 + 1;
        //dp解法： dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]] ;背包问题，当前石块要或者不要
        //解释为前i个元素是否可以组和为j
        vector<vector<bool>> dp(row , vector<bool>(col , false));
        if(nums[0] < col) dp[0][nums[0]] = true;
        for(int i=0;i<row;++i) dp[i][0] = true;
        for(int i = 1; i < row; ++i){
            for(int j = 1; j < col; ++j){
                if(j >= nums[i]){
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]] ;
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[row-1][col-1] != 0;
    }
};

//编写一个函数，传入一个int型数组，返回该数组能否分成两组，使得两组中各元素加起来的和相等，
//并且，所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），能满足以上条件，返回true；不满足时返回false。 
class split_2{
public:
    bool backtrace(vector<int>& arr,int sum3,int sum5,int index){
        if(index == arr.size() && sum3 != sum5) return false;
        if(index == arr.size() && sum3 == sum5) return true;
        return backtrace(arr,sum3+arr[index],sum5,index+1) || backtrace(arr,sum3,sum5+arr[index],index+1);
    }
    bool operator()(vector<int>& nums){
        int sum5 = 0;
        int sum3 = 0;
        vector<int> array;
        for(int& val:nums){
            if(val%5 == 0) sum5 += val;
            else if(val%3 == 0) sum3 += val;
            else array.push_back(val);
        }
        return backtrace(array,sum3,sum5,0);
    }

};




int main()
{
    split_1 obj1;
    split_2 obj2;
    vector<int> nums{1,1,1,1,2,2};
    if(obj1(nums))
        cout << "true\n";
    vector<int> nums1{5,3,1,1,1,1,2,2,2};
    if(obj2(nums1))
        cout << "true\n";
    return 0;
}